package codeRandomThoughts.Test862和至少为K的最短子数组;

/**
 * 会超时,服了
 */
public class Solution {
    public int shortestSubarray(int[] nums, int k) {
        //保存以i结尾的最靠近k的最大和和长度
        int[][] maxSumLength = new int[nums.length][2];

        maxSumLength[0][0] = nums[0];
        maxSumLength[0][1] = 1;
        for (int i = 1; i < nums.length; i++) {
            //如果以前一项结尾的最大值>0,那么本项接上前一项
            if (maxSumLength[i - 1][0] > 0) {
                //如果此时最大和大于k,我们尝试缩小区间范围
                int len = maxSumLength[i - 1][1] + 1;
                int sum = maxSumLength[i - 1][0] + nums[i];
                maxSumLength[i][0] = sum;
                maxSumLength[i][1] =len;
                if (sum>=k){
                    for (int j = i - len + 1; j < i; j++) {
                        System.out.println("测试去除"+j);
                        sum -= nums[j];
                        if (sum >= k) {
                            System.out.println(sum);
                            maxSumLength[i][0] = sum;
                            maxSumLength[i][1] = i - j + 1;
                        }
                    }
                }

            } else {
                //从本项开始重新计算最大值
                maxSumLength[i][0] = nums[i];
                maxSumLength[i][1] = 1;
            }
        }

        int len = Integer.MAX_VALUE;
        for (int[] ints : maxSumLength) {
            System.out.println("sum"+ints[0]);
            System.out.println("len"+ints[1]);
            if (ints[0] >= k) {
                if (ints[1] < len) {
                    len = ints[1];
                }
            }
        }

        //如果len没变过,说明没有符合题意的解
        if (len == Integer.MAX_VALUE) return -1;
        return len;
    }
}
